// m

// 给定一个整数n，求以1到n为节点构成的二叉搜索树有多少种

// 解题思路：动态规划
// 1到n的每个节点都可以用来做根节点，每个根节点i都是由左子树（1,2,3，..., i-1）和右子树（i+1, i+2, ..., n）构成的，则二叉搜索树的个数肯定是两个子树个数的乘积，而根节点有n个
// 最终将这些个数累加起来即可

// 1.定义f[i]为以i为根节点的二叉搜索树个数，dp[i]为i个节点构成的二叉搜索树个数，则
// dp[i] = f(1) + f(2) + ... + f(i)
// 当i为根节点时，其左子树节点个数为i-1，右节点个数为n-i，则f(i) = dp[i-1] * dp[n-i]
// 综上所述，定义状态dp[i]表示：i个节点构成的二叉搜索树个数
// 状态转移方程为dp[i] = dp[0] * dp[i-1] + dp[1] * dp[i-2] + ... + dp[i-1] * dp[0]
// 即：dp[i] += dp[j-1] * dp[i-j], 1 <= j <= i

function numTrees(n) {
    let dp = new Array(n + 1).fill(0)
    dp[0] = 1
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < i + 1; j++) {
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp[n]
}

let n = 3
console.log(numTrees(n))